#include <iostream>
using namespace std;

/// @brief 双链表
typedef struct DNode // 定义双链表节点类型
{
    int daya;                   // 数据域
    struct DNode *prior, *next; // 前驱和后继指针
} DNode, *DLinkList;

/*
//后向遍历
while(p!=NULL){
 p=p->next;
}

//前向遍历
while(p!=NULL){
    p=p->prior;
}

//向前遍历（跳过头结点）
while(p->prior!=NULL){
    p=p->prior;
}

*/

/// @brief 初始化双链表
/// @param L
/// @return
bool InitDLinkList(DLinkList &L)
{
    L = (DNode *)malloc(sizeof(DNode)); // 分配一个头结点
    if (L == NULL)
    { // 内存不足，分配失败
        return false;
    }
    L->prior = NULL;
    L->next = NULL;
    return true;
}

/// @brief 判断双链表是否为空（带头节点）
/// @param L
/// @return
bool Empty(DLinkList L)
{
    if (L->next == NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
}

/// @brief 双链表的插入：咋p节点之后插入s节点
/// @param p
/// @param s
/// @return
bool InsertNextDNode(DNode *p, DNode *s)
{
    if (p == NULL || s == NULL)
    { // 非法参数
        return false;
    }
    s->next = p->next;
    if (p->next != NULL)
    {
        p->next->prior = s;
    }
    s->prior = p;
    s->next = s;
    return true;
}

/// @brief 双链表删除p节点的后继结点
/// @param p
/// @return
bool DeleteNextDNode(DNode *p)
{
    if (p == NULL)
    {
        return false;
    }
    DNode *q = p->next; // 找到p的后继结点q
    if (q == NULL)
    {
        return false; // p没有后继节点
    }
    p->next = q->next;
    if (q->next != NULL)
    { // q节点不是最后一个节点
        q->next->prior = p;
    }
    free(q); // 释放节点空间
    return true;
}

/// @brief 双链表的删除
/// @param L
void DestroyList(DLinkList &L)
{
    // 循环释放各个数据节点
    while (L->next != NULL)
    {
        DeleteNextDNode(L);
    }
    free(L);  // 释放头结点
    L = NULL; // 头指针指向NULL
}